/*
 * @lc app=leetcode.cn id=28 lang=csharp
 *
 * [28] 找出字符串中第一个匹配项的下标
 */

// @lc code=start
public class Solution {
    public int StrStr(string _string, string pattern) {
        if(pattern.Length == 0)
        {
            return 0;
        }
        int[] next = new int[pattern.Length];
        next[0] = -1;
        int i = 0, j = -1;
        while(i < pattern.Length - 1)
        {
            if(j == -1 || pattern[i] == pattern[j])
            {
                next[++i] = ++j;
            }
            else
            {
                j = next[j];
            }
        }
        i = 0;
        j = 0;
        while(i < _string.Length && j < pattern.Length)
        {
            if(j == -1 || _string[i] == pattern[j])
            {
                ++i;
                ++j;
            }
            else
            {
                j = next[j];
            }
        }
        return j == pattern.Length ? i - j : -1;
    }
}
// @lc code=end

/* *
a a a a a a c a b b
a a a a b

a b c a b c a b b
a b c a b b

a a c a b c a b
a a b
*/

